use std::collections::HashSet;
use std::io::Write;

use super::check::check_coord_for_grid;
use super::search::*;

// Copy thu
pub fn route_single_target_path_with_len(
    grid: &mut Grid,
    start: Coord,
    target: Coord,
    bus_len: usize,
    color: Color,
) -> Result<Vec<Coord>, String> {
    check_coord_for_grid(grid, start)?;
    check_coord_for_grid(grid, target)?;

    let mut fixed_path = Vec::new();
    let mut start = start;
    let len = start.manhattan_distance(&target) as usize;
    if len > bus_len {
        return Err(format!("len '{len}' > bus_len '{bus_len}'"));
    }
    if (bus_len - len) % 2 == 1 {
        return Err(format!(
            "(bus_len - len) % 2 = '{}' == 1",
            (bus_len - len) % 2 == 1
        ));
    }
    if start.y as usize <= (bus_len - len) / 2 {
        return Err(format!("start.y '{}' < '{}'", start.y, (bus_len - len) / 2));
    }

    for _ in 0..(bus_len - len) / 2 {
        grid.set_cell(start, Cell::Routed(color));
        fixed_path.push(start);
        start.y -= 1;
    }

    match search_single_target_path(grid, start, target) {
        Ok(path) => {
            for coord in &path {
                grid.set_cell(*coord, Cell::Routed(color));
            }
            fixed_path.extend(path);
            Ok(fixed_path)
        }
        Err(err) => {
            for coord in fixed_path {
                grid.set_cell(coord, Cell::Empty);
            }
            Err(err)
        }
    }
}

pub fn route_single_target_path_with_len_recur(
    grid: &mut Grid,
    start: Coord,
    target: Coord,
    path_len: usize,
    color: Color,
) -> Result<Vec<Coord>, String> {
    // if path_len > MAX_RECURSION_LEN {
    //     return Err(format!("'{path_len}' recursion too deep"));
    // }

    check_coord_for_grid(grid, start)?;
    check_coord_for_grid(grid, target)?;

    let mut path = Vec::new();
    let mut used = HashSet::new();
    path.push(start);
    used.insert(start);

    match do_route_single_target_with_len_recur(
        grid,
        start,
        target,
        path_len - 1,
        &mut path,
        &mut used,
    ) {
        false => Err("Route failed".to_string()),
        true => {
            assert_eq!(path.len(), path_len);
            for coord in &path {
                grid.set_cell(*coord, Cell::Routed(color));
            }
            Ok(path)
        }
    }
}

// Single route && Partial Recursion
pub fn route_single_target_path_with_len_partial_recur(
    grid: &mut Grid,
    start: Coord,
    target: Coord,
    path_len: usize,
    color: Color,
) -> Result<Vec<Coord>, String> {
    const RATIO: f64 = 0.1;

    check_coord_for_grid(grid, start)?;
    check_coord_for_grid(grid, target)?;

    let path = search_single_target_path(grid, start, target)?;

    use std::cmp::Ordering;
    match path.len().cmp(&path_len) {
        Ordering::Greater => Err("Route failed".into()),
        Ordering::Equal => Ok(path),
        Ordering::Less => {
            std::io::stdout().flush().unwrap();
            let delete_coord_size = (path.len() as f64 * RATIO) as usize;
            if delete_coord_size == 0 {
                return route_single_target_path_with_len_recur(
                    grid, start, target, path_len, color,
                );
            }

            // Set coords to Routed
            let remain_coord_size = path.len() - delete_coord_size;
            for coord in path.iter().take(remain_coord_size) {
                grid.set_cell(*coord, Cell::Routed(color));
            }

            let cur_start = path[remain_coord_size];
            let cur_target_path_len = (path_len - path.len()) + delete_coord_size;
            match route_single_target_path_with_len_recur(
                grid,
                cur_start,
                target,
                cur_target_path_len,
                color,
            ) {
                Ok(left_path) => {
                    let total_path = path
                        .into_iter()
                        .take(remain_coord_size)
                        .chain(left_path.into_iter())
                        .collect();
                    Ok(total_path)
                }
                Err(err) => {
                    for coord in path.iter().take(remain_coord_size) {
                        grid.set_cell(*coord, Cell::Empty);
                    }
                    Err(err)
                }
            }
        }
    }
}

pub fn route_single_target_path_with_len_multi_partial_recur(
    grid: &mut Grid,
    start: Coord,
    target: Coord,
    path_len: usize,
    color: Color,
) -> Result<Vec<Coord>, String> {
    check_coord_for_grid(grid, start)?;
    check_coord_for_grid(grid, target)?;

    let path = search_single_target_path(grid, start, target)?;

    use std::cmp::Ordering;
    match path.len().cmp(&path_len) {
        Ordering::Greater => Err("Route failed".into()),
        Ordering::Equal => Ok(path),
        Ordering::Less => {
            /*

                delta_len = path_len - path.len();
                let Recur size = MAX, (min recur size)
                
                path.len()?


            */


            let mut target_path_lens = target_path_lens(path_len);
            let paths = divide_path(&path, target_path_lens.len());
            assert_eq!(target_path_lens.len(), paths.len());

            let mut totoal_target_path_len = 0;
            for (i, &sub_path) in paths.iter().enumerate() {
                let start = sub_path.first().unwrap();
                let end = sub_path.last().unwrap();
                let path_len = if (SUIT_RECURSION_LEN - (start.manhattan_distance(end) as usize)) % 2 == 1 {
                    SUIT_RECURSION_LEN
                } else {
                    SUIT_RECURSION_LEN + 1
                };

                target_path_lens[i] = path_len;
                totoal_target_path_len += path_len;
            }

            use std::cmp::Ordering;
            match totoal_target_path_len.cmp(&path_len) {
                Ordering::Equal => {}
                Ordering::Greater => {
                    let over_len = totoal_target_path_len - path_len;
                    if over_len % 2 == 1 {
                        return Err(format!("Route failed for net length not suitable"));
                    }
                    for len in target_path_lens.iter_mut()
                        .rev()
                        .filter(|l| **l == SUIT_RECURSION_LEN + 1)
                        .take(over_len / 2) 
                    {   
                        *len = SUIT_RECURSION_LEN - 1;
                    }
                }
                Ordering::Less => unreachable!(),
            }

            let mut final_path = Vec::new();
            for (&target_len, &sub_path) in Iterator::zip(target_path_lens.iter(), paths.iter()) {
                // println!("route from '{:?}' to '{:?}' with {target_len}", sub_path.first().unwrap(), sub_path.last().unwrap());
                match route_single_target_path_with_len_recur(
                    grid, 
                    *sub_path.first().unwrap(), 
                    *sub_path.last().unwrap(), 
                    target_len, color) {
                    Ok(success_path) => {
                        final_path.extend(success_path.into_iter());
                    }
                    Err(err) => {
                        // Reset all used_coords
                        for coord in final_path {
                            grid.set_cell(coord, Cell::Empty);
                        }
                        return Err(err)
                    }
                }
            }

            Ok(final_path)
        }
    }
}

const MAX_RECURSION_LEN: usize = 8;
const SUIT_RECURSION_LEN: usize = MAX_RECURSION_LEN - 2;

fn target_path_lens(total_path_len: usize) -> Vec<usize> {
    if total_path_len <= SUIT_RECURSION_LEN {
        return vec![total_path_len];
    }

    let ram = total_path_len % SUIT_RECURSION_LEN;
    let quot = total_path_len / SUIT_RECURSION_LEN;
    
    let mut res = vec![SUIT_RECURSION_LEN; quot];
    if ram != 0 {
        res.push(ram);
    }

    res
}

fn divide_path(path: &[Coord], divide_size: usize) -> Vec<&[Coord]> {
    assert!(path.len() > divide_size);

    // return vec's len == divide_size !!!
    if divide_size == 1 {
        return vec![&path[..]];
    }

    let total_len = path.len();
    let ram = total_len % divide_size;
    let quot = total_len / divide_size;

    // 6 8

    let partial_lens = if ram == 0 {
        vec![quot; divide_size]
    } else {
        let mut partial_lens = vec![quot; divide_size];
        for i in 0..ram {
            partial_lens[i] += 1;
        }
        partial_lens
    };

    assert_eq!(total_len, partial_lens.iter().sum::<usize>());

    let mut begin = 0;
    let mut res = Vec::new();
    for partial_len in partial_lens {
        res.push(&path[begin..begin+partial_len]);
        begin += partial_len;
    }

    res
}

fn do_route_single_target_with_len_recur(
    grid: &Grid,
    start: Coord,
    target: Coord,
    path_len: usize,
    path: &mut Vec<Coord>,
    used: &mut HashSet<Coord>,
) -> bool {
    if path_len == 0 {
        return start == target;
    } else if start == target {
        return false;
    }

    for next_coord in start.adjacent_coords() {
        if grid.is_valid_coord(next_coord)
            && grid.cell(next_coord).unwrap().is_empty()
            && !used.contains(&next_coord)
        {
            path.push(next_coord);
            used.insert(next_coord);

            if do_route_single_target_with_len_recur(
                grid,
                next_coord,
                target,
                path_len - 1,
                path,
                used,
            ) {
                return true;
            }

            path.pop();
            used.remove(&next_coord);
        }
    }

    false
}

#[cfg(test)]
mod test {
    use crate::drawer::write_png;
    use super::*;

    #[test]
    fn test_route_single_target_with_len_recur1() {
        let s = Coord::new(1, 5);
        let e = Coord::new(2, 6);
    
        let mut grid = Grid::new(15, 15);
        match route_single_target_path_with_len_recur(&mut grid, s, e, 5, Color::green()) {
            Ok(path) => println!("Route success with len: {}", path.len()),
            Err(msg) => println!("{}", msg),
        }
        write_png(&grid, "./pic/test_route_single_target_with_len_recur1.png");
    }

    #[test]
    fn test_route_single_target_with_len_recur2() {
        let s = Coord::new(1, 5);
        let e = Coord::new(2, 6);
    
        let mut grid = Grid::new(15, 15);
        match route_single_target_path_with_len_recur(&mut grid, s, e, 9, Color::green()) {
            Ok(path) => println!("Route success with len: {}", path.len()),
            Err(msg) => println!("{}", msg),
        }
        write_png(&grid, "./pic/test_route_single_target_with_len_recur2.png");
    }

    #[test]
    fn test_route_single_target_with_len_recur3() {
        let s = Coord::new(1, 5);
        let e = Coord::new(2, 6);
    
        let mut grid = Grid::new(15, 15);
        match route_single_target_path_with_len_recur(&mut grid, s, e, 13, Color::green()) {
            Ok(path) => println!("Route success with len: {}", path.len()),
            Err(msg) => println!("{}", msg),
        }
        write_png(&grid, "./pic/test_route_single_target_with_len_recur3.png");
    }
    
    #[test]
    fn test_route_single_target_path_with_len_partial_recur1() {
        let s = Coord::new(1, 5);
        let e = Coord::new(12, 16);
    
        let mut grid = Grid::new(20, 20);
        match route_single_target_path_with_len_partial_recur(&mut grid, s, e, 29, Color::green()) {
            Ok(path) => println!("Route success with len: {}", path.len()),
            Err(msg) => println!("{}", msg),
        }
        write_png(
            &grid,
            "./pic/route_single_target_path_with_len_partial_recur1.png",
        );
    }
    
    #[test]
    fn test_route_single_target_path_with_len_partial_recur2() {
        let s = Coord::new(20, 84);
        let e = Coord::new(120, 105);
    
        let mut grid = Grid::new(150, 150);
        match route_single_target_path_with_len_partial_recur(&mut grid, s, e, 140, Color::green()) {
            Ok(path) => println!("Route success with len: {}\n{:?}", path.len(), path),
            Err(msg) => println!("{}", msg),
        }
        write_png(
            &grid,
            "./pic/route_single_target_path_with_len_partial_recur2.png",
        );
    }

    #[test]
    fn test_route_single_target_path_with_len_multi_partial_recur1() {
        let s = Coord::new(1, 5);
        let e = Coord::new(12, 16);
    
        let mut grid = Grid::new(20, 20);
        match route_single_target_path_with_len_multi_partial_recur(&mut grid, s, e, 29, Color::green()) {
            Ok(path) => println!("Route success with len: {}", path.len()),
            Err(msg) => println!("{}", msg),
        }
        write_png(
            &grid,
            "./pic/test_route_single_target_path_with_len_multi_partial_recur1.png",
        );
    }
    
    #[test]
    fn test_route_single_target_path_with_len_multi_partial_recur2() {
        let s = Coord::new(20, 84);
        let e = Coord::new(120, 105);
    
        let mut grid = Grid::new(150, 150);
        match route_single_target_path_with_len_multi_partial_recur(&mut grid, s, e, 150, Color::red()) {
            Ok(path) => println!("Route success with len: {}\n{:?}", path.len(), path),
            Err(msg) => println!("{}", msg),
        }
        write_png(
            &grid,
            "./pic/test_route_single_target_path_with_len_multi_partial_recur2.png",
        );
    }

    #[test]
    fn test_target_path_lens() {
        assert_eq!(
            target_path_lens(27),
            vec![8, 8, 8, 3]
        );

        println!("{:?}", target_path_lens(150));
        println!("{:?}", target_path_lens(150).len());
    }

    #[test]
    fn test_divide_path() {
        let path: Vec<_> = (0..21).into_iter().map(|x| Coord::new(x, 10)).collect();
        let res = divide_path(&path, 4);

        assert_eq!(
            res.into_iter().map(|p| p.len()).collect::<Vec<_>>(),
            vec![6, 5, 5, 5]
        );

        let path: Vec<_> = (0..122).into_iter().map(|x| Coord::new(x, 10)).collect();
        let res = divide_path(&path, 19);   
        println!("{:?}", res.into_iter().map(|p| p.len()).collect::<Vec<_>>());
    }
}